package embuzzled.g5;

import java.awt.Color;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Random;

import embuzzled.ui.Grid;

public class PuzzleGrid 
{
	Color[][] grid;
	
	int rows, cols;
	
	//Number of times we try placing a standalone puzzle randomly before we give up.
	public static int maxPlacementAttempts;
	
	Random r;
	
	//Solution to each puzzle
	String solution;
	
	//Number of placed puzzles
	int numPuzzles;
	
	//The location of the last placed puzzle.
	Point lastPlaced;
	
	public PuzzleGrid(Grid grid)
	{
		this.grid = generateInitialColorMap(grid);
		rows = grid.rows;
		cols = grid.cols;
		maxPlacementAttempts = rows * cols;
		r = Helper.rand;
		solution = "Answer Key:" + "\r\n" + "Theme: Sky" + "\r\n";
		numPuzzles = 0;
	}
	
	public void populate(PuzzleSet possiblePuzzles)
	{
		//System.out.println("Populating...");
		int numPuzzles = possiblePuzzles.getSize();
		
		// Naive - tries to add all puzzles
		for(int i = 0; i < numPuzzles; i++)
		{
			//System.out.println("Attempting to add puzzle " + i);
			Puzzle p = possiblePuzzles.get(i);
			addPuzzle(p);
		}
	}
	
	/**
	 *  Attempts to add a puzzle to this grid.
	 *  Updates the color map and the solution if it
	 *  was added successfully.
	 * @param p A puzzle.
	 * @return True if it was added successfully. False otherwise.
	 */
	public boolean addPuzzle(Puzzle p)
	{
		Color[][] newGrid;
		
		if(p.isComposite())
		{
			//System.out.println("Composite puzzle");
			newGrid = addCompositePuzzle(grid, p);
		}
		else
		{
			//System.out.println("Standalone puzzle");
			newGrid = addStandalonePuzzle(grid, p);
		}
		
		if(newGrid != null)
		{
			//System.out.println("Puzzle added!");
			grid = newGrid;
			solution = solution + (numPuzzles + 1) + ".) Row " + lastPlaced.x + ", Column " + lastPlaced.y + ": ";
			solution = solution + p.getSolution() + "\r\n";
			numPuzzles++;
			return true;
		}
		else
		{
			//System.out.println("Adding failed");
			return false;
		}
	}
	
	/**
	 * Attempts to add a standalone (non-composite) puzzle to the grid.
	 * Uses the placement strategies given by the puzzle.
	 * If adding can succeed, then this method returns a color map
	 * representing the current state of this grid with the puzzle added.
	 * If the puzzle cannot be added, then it returns null.
	 * @param grid A color map.
	 * @param p A non-composite puzzle.
	 * @return "grid" with the puzzle added if possible. Null if not.
	 */
	public Color[][] addStandalonePuzzle(Color[][] grid, Puzzle p)
	{
		int[] strats = p.getPlacementStrategies();
		strats = Helper.permuteArray(strats);
		
		Color[][] newMap = null;
		
		//Try all strategies in order, naive
		for(int currentStrat : strats)
		{
			if(currentStrat == Constants.PLACEMENT_ANYWHERE)
				newMap = randomPlacement(grid, p);
			
			if(newMap != null)
			{
				//Adding succeeded
				return newMap;
			}
				
		}
			
		return null; //No strategy worked
	}
	
	/**
	 * Try random spots on the grid to place the puzzle.
	 * Returns null if failed attempts exceeds MAX_PLACEMENT_ATTEMPTS.
	 * Returns the map with the puzzle added if it succeeds.
	 * @param grid A color map.
	 * @param p A non-composite puzzle.
	 * @return The grid with puzzle p added if possible. Null if not.
	 */
	public Color[][] randomPlacement(Color[][] grid, Puzzle p)
	{
		//System.out.println("Random placement");
		Color[][] puzzleMap = p.returnLocalColorMap();
		Color[][] newMap = null;
		
		int attempts = 0;
		
		Point pp = new Point(0,0);
		
		while(attempts < maxPlacementAttempts/2 && newMap == null)
		{
			//Pick a random point in the grid
			// Choose a random point in the grid and start searching 
			//for the biggest open space.
			// it returns the left-most point of the biggest rectangle 
			// that can be found in the grid. 
			//the freespace method takes in a random point to start with 
			// so that the placement of the puzzles is not linear.
			
			Point pt = new Point(r.nextInt(grid[0].length), r.nextInt(grid.length));
			pp = freespace(grid, pt);
			
			//Attempt to superimpose the puzzle on the grid at that point
			//newMap != null when succeeds, so while loop terminates
			newMap = Helper.superimpose(grid, puzzleMap, pp);
			
			//Time out and return null after enough tries.
			attempts++;
		}
		
		while(attempts < maxPlacementAttempts && newMap == null)
		{
			//Freespace fails, just choose random points
			
			pp = new Point(r.nextInt(grid[0].length), r.nextInt(grid.length));
			
			//Attempt to superimpose the puzzle on the grid at that point
			//newMap != null when succeeds, so while loop terminates
			newMap = Helper.superimpose(grid, puzzleMap, pp);
			
			//Time out and return null after enough tries.
			attempts++;
		}
		
		
		
		if(newMap != null)
		{
			//System.out.println("Random placement succeeded.");
			lastPlaced = new Point(pp.y, pp.x);
		}
		
		return newMap;
	}
	
	public Point freespace(Color[][] grid, Point p) {
		
		int rows = grid.length;
		int cols = grid[0].length;
		int sum[][] = new int[rows + 10][cols + 10];	
		for(int i=0;i<=rows;i++){
			for(int j=0;j<=cols;j++){
				sum[i][j] = 0 ;
			}
		}
		for(int i=1;i<=rows;i++){
			 for(int j=1;j<=cols;j++)
			 {
				 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] ;
				 if(!grid[i-1][j-1].equals(Constants.COLOR_CLEAR))
						sum[i][j] ++ ;
			 }
		}
				 
		
		//int x = 0;
		//int y = 0;
		int area = 0 ;
		Point pp = new Point();
		for(int r = p.x; r < rows; r++){
			for(int c = p.y; c < cols; c++){
				for(int rr=r;rr<rows;rr++){
					for(int cc =c;cc<rows;cc++)
					{
						boolean valid = true ;
						int arr = sum[rr+1][cc+1] ;
						arr -= sum[r][cc+1] + sum[rr + 1][c] ;
						arr += sum[r][c] ;
						if(arr > 0) valid = false ;
						if(valid && (rr - r + 1)*(cc - c + 1) > area)
						{
							area = (rr - r + 1)*(cc - c + 1) ;
							pp.x = r ; pp.y = c ;
						}
					}
				}
			}
		}
		return pp;
	}
	
	public Color[][] addCompositePuzzle(Color[][] grid, Puzzle p)
	{
		int[] strats = p.getPlacementStrategies();
		strats = Helper.permuteArray(strats);
		
		Color[][] newMap = null;
		
		CompositePuzzle cp = (CompositePuzzle)p;
		
		//Try all strategies in order, naive
		for(int currentStrat : strats)
		{
			//System.out.println("Trying strategy " + currentStrat);
			if(currentStrat == Constants.PLACEMENT_HORIZONTAL)
				newMap = horizontalRandomSequencePlacement(grid, cp);
			else if(currentStrat == Constants.PLACEMENT_VERTICAL_DOWN)
				newMap = verticalDownRandomSequencePlacement(grid, cp);
			else if(currentStrat == Constants.PLACEMENT_DIAGONAL_DOWN_RIGHT)
				newMap = diagonalDownRightRandomSequencePlacement(grid, cp);
			
			if(newMap != null)
			{
				//Adding succeeded
				return newMap;
			}
				
		}
			
		return null; //No strategy worked
	}
	
	
	/**
	 *  Tries to add a composite puzzle to the grid.
	 *  It picks a random cell in the first row, and tries to add the
	 *  first component. If that succeeds, it tries to add each successive
	 *  component down that column.
	 *  Else, it tries adding the first component exhaustively.
	 * @param grid A color map.
	 * @param p A composite puzzle.
	 * @return The grid containing this puzzle if possible. Null if not.
	 */
	public Color[][] verticalDownSequencePlacement(Color[][] grid, Puzzle p)
	{
		//System.out.println("Vertical down sequence placement.");
		ArrayList<PuzzleComponent> components = p.getComponents();
		
		//Current row/col we are placing a component in
		int row = 0;
		int col = r.nextInt(cols);
		
		//Current component we are placing
		int comp = 0;
		
		//How many columns we have tried when placing the first component
		int colsTried = 0;
		
		//Has the puzzle been placed yet?
		boolean placed = false;
		
		PuzzleComponent currentComponent = components.get(comp);
		Color[][] currentComponentMap = currentComponent.returnLocalColorMap();
		
		Color[][] currentGrid = grid;
		Color[][] newGrid = grid;
		
		Point pt = new Point(col, row);
		
		while(!placed)
		{
			pt = new Point(col,row);
			newGrid = Helper.superimpose(currentGrid, currentComponentMap, pt);
			
			if(newGrid != null)
			{
				//Added component successfully.
				//System.out.println("Added component " + comp + " to [" + row + ", " + col + "]");
				
				//Keep the new grid.
				currentGrid = newGrid;
				
				//Look at the row beneath the added com
				row += currentComponentMap.length + 1;
				comp += 1;
				
				//Added all components - return success
				if(comp == components.size())
				{
					//System.out.println("All components successfully added.");
					return newGrid;
				}
					
				
				//else, prepare to add next component
				currentComponent = components.get(comp);
				currentComponentMap = currentComponent.returnLocalColorMap();
			}
			else if(newGrid == null && comp == 0 && colsTried < cols)
			{
				//Failed to add first component
				//Check next column, wrapping if necessary.
				////System.out.println("Failed to add first component to [" + row + ", " + col + "]");
				////System.out.println("Looking at next column");
				col = (col + 1) % cols;
				colsTried++;
			}
			else if(newGrid == null && comp == 0 && row < rows)
			{
				//Failed to add first component to each column in a row
				////System.out.println("Failed to add first component to row " + row);
				////System.out.println("Checking next row");
				//Check next row
				col = (col + 1) % cols;
				colsTried = 0;
				row++;
			}
			else if(newGrid == null && comp == 0 && row == rows)
			{
				//Cannot add first component, return null.
				//System.out.println("Cannot add first component anywhere");
				return null;
			}
			else if(newGrid == null && row < rows)
			{
				////System.out.println("Cannot add component " + comp + " to row " + row);
				//Cannot add nth component.
				//Check next row.
				//Might want code to ensure equal spacing?
				row++;
			}
			else
			{
				//Cannot place all components.
				return null;
			}
		}
		
		
		return null;
	}
	

	/**
	 *  Tries to add a composite puzzle to the grid.
	 *  It picks a random cell in the grid, and tries to add the
	 *  first component. If that succeeds, it tries to add each successive
	 *  component across that row, evenly spaced.
	 *  Else, it tries adding the first component exhaustively.
	 * @param grid A color map.
	 * @param p A composite puzzle.
	 * @return The grid containing this puzzle if possible. Null if not.
	 */
	public Color[][] horizontalRandomSequencePlacement(Color[][] grid, CompositePuzzle p)
	{
		//System.out.println("Horizontal sequence placement.");
		ArrayList<PuzzleComponent> components = p.getComponents();
		

		int maxRow = rows - p.getWidthSpaced();
		int maxCol = cols - p.getHeightSpaced();
		
		//Current row/col we are placing a component in
		int row = r.nextInt(rows);
		int col = r.nextInt(cols);
		
		//Choose starting point with best free space
		Point pp = freespace(grid, new Point(row, col));
		row = pp.x;
		col = pp.y;
		
		//Location of first component, for backtracking
		int row2 = 0;
		int col2 = 0;
		
		//Location of second component, for backtracking
		int row3 = 0;
		int col3 = 0;
		
		//Current component we are placing
		int comp = 0;
		
		//How many columns we have tried when placing the first component
		int rowsTried = 0;
		int colsTried = 0;
		
		//Even spacing between letters
		int spacing = 1;
		
		//Has the puzzle been placed yet?
		boolean placed = false;
		boolean forceFail = false;
		
		PuzzleComponent currentComponent = components.get(comp);
		Color[][] currentComponentMap = currentComponent.returnLocalColorMap();
		
		Color[][] currentGrid = grid;
		Color[][] newGrid = grid;
		
		//Grid containing the placed first component
		Color[][] firstCompGrid = grid;
		
		Point pt = new Point(col, row);
		
		while(!placed)
		{
			pt = new Point(col,row); //Point to try placing the current component
			
			if(!forceFail)
				newGrid = Helper.superimpose(currentGrid, currentComponentMap, pt);
			else
			{
				newGrid = null;
				forceFail = false;
			}
				
			
			if(newGrid != null && comp == 0)
			{
				//Added first component successfully
				//System.out.println("Added first component to [" + row + ", " + col + "]");
				
				currentGrid = newGrid;
				
				//Store this so we can iterate on spacing if necessary.
				firstCompGrid = newGrid;
				
				//Store position of first component for possible iteration.
				row2 = row;
				col2 = col;
				
				spacing = 1;
				
				//Look at next column
				col += currentComponentMap[0].length + spacing;
				comp++;
				
				
				
				
				//Added all components, success
				if(comp == components.size())
				{
					//System.out.println("All components added.");
					lastPlaced = new Point(row2, col2);
					return newGrid;
				}
				else
				{
					currentComponent = components.get(comp);
					currentComponentMap = currentComponent.returnLocalColorMap();
				}
				
				
			}
			
			else if(newGrid != null && comp != 0)
			{
				//System.out.println("Added component " + comp + " to [" + row + ", " + col + "]");
				
				currentGrid = newGrid;
				
				if(comp == 1)
				{

					//Store position of second component for iterating spacing
					row3 = row;
					col3 = col;
				}
				
				col += currentComponentMap[0].length + spacing;
				comp++;
				
				
				
				if(comp == components.size())
				{
					//System.out.println("All components added.");
					lastPlaced = new Point(row2, col2);
					return newGrid;
				}
				else
				{
					currentComponent = components.get(comp);
					currentComponentMap = currentComponent.returnLocalColorMap();
				}
			}
			
			else if(newGrid == null && comp == 0)
			{
				//Exhaustive search starting at random point
				//Try cols, then rows
				if(colsTried < maxCol)
				{
					//System.out.println("Try next col");
					col = (col + 1) % maxCol;
					colsTried++;
				}
				else
				{
					//System.out.println("Try next row");
					col = (col + 1) % maxCol;
					colsTried = 0;
					
					row = (row + 1) % maxRow;
					rowsTried++;
					
					if(rowsTried > maxRow)
					{
						//System.out.println("All possible spots failed.");
						return null;
					}
					
				}
			}
			else if (newGrid == null && comp == 1)
			{
				if(col < cols - currentComponentMap.length)
				{
					//System.out.println("Try next col");
					//Try next col
					col++;
					spacing++;
				}
				else
				{
					//System.out.println("Adding second component failed. Replace first component.");
					//Couldn't place second component. Look at next placement for first component.
					currentGrid = grid;
					currentComponentMap = components.get(0).returnLocalColorMap();
					comp = 0;
					row = row2;
					col = col2;
					forceFail = true;
				}
			}
			else if (newGrid == null && comp > 1)
			{
				//Couldn't place nth component. Spacing wrong for second component, perhaps.
				
				//Reset to state after placing first component
				
				//System.out.println("Adding component " + comp + " failed. Replace second component.");
				currentGrid = firstCompGrid;
				comp = 1;
				
				currentComponent = components.get(1);
				currentComponentMap = currentComponent.returnLocalColorMap();
				
				//Try placing the second component to the right one column
				col3++;
				col = col3;				
				spacing++;
			}
			else
			{
				return null;
			}
			
		}
		
		
		return null;
	}
	
	/**
	 *  Tries to add a composite puzzle to the grid.
	 *  It picks a random cell in the first row, and tries to add the
	 *  first component. If that succeeds, it tries to add each successive
	 *  component down that column.
	 *  Else, it tries adding the first component exhaustively.
	 * @param grid A color map.
	 * @param p A composite puzzle.
	 * @return The grid containing this puzzle if possible. Null if not.
	 */
	public Color[][] verticalDownRandomSequencePlacement(Color[][] grid, CompositePuzzle p)
	{
		//System.out.println("Vertical sequence placement.");
		ArrayList<PuzzleComponent> components = p.getComponents();
		

		int maxRow = rows - p.getWidthSpaced();
		int maxCol = cols - p.getHeightSpaced();
		
		//Current row/col we are placing a component in
		int row = r.nextInt(rows);
		int col = r.nextInt(cols);
		
		Point pp = freespace(grid, new Point(row, col));
		row = pp.x;
		col = pp.y;
		
		int row2 = 0;
		int col2 = 0;
		
		int row3 = 0;
		int col3 = 0;
		
		//Current component we are placing
		int comp = 0;
		
		//How many columns we have tried when placing the first component
		int rowsTried = 0;
		int colsTried = 0;
		
		//Even spacing between letters
		int spacing = 1;
		
		//Has the puzzle been placed yet?
		boolean placed = false;
		boolean forceFail = false;
		
		PuzzleComponent currentComponent = components.get(comp);
		Color[][] currentComponentMap = currentComponent.returnLocalColorMap();
		
		Color[][] currentGrid = grid;
		Color[][] newGrid = grid;
		
		//Grid containing the placed first component
		Color[][] firstCompGrid = grid;
		
		Point pt = new Point(col, row);
		
		while(!placed)
		{
			pt = new Point(col,row); //Point to try placing the current component
			
			if(!forceFail)
				newGrid = Helper.superimpose(currentGrid, currentComponentMap, pt);
			else
			{
				newGrid = null;
				forceFail = false;
			}
				
			
			if(newGrid != null && comp == 0)
			{
				//Added first component successfully
				//System.out.println("Added first component to [" + row + ", " + col + "]");
				
				currentGrid = newGrid;
				
				//Store this so we can iterate on spacing if necessary.
				firstCompGrid = newGrid;
				
				//Store position of first component for possible iteration.
				row2 = row;
				col2 = col;
				
				spacing = 1;
				
				//Look at next row
				row += currentComponentMap.length + spacing;
				comp++;
				
				
				
				
				//Added all components, success
				if(comp == components.size())
				{
					//System.out.println("All components added.");
					lastPlaced = new Point(row2, col2);
					return newGrid;
				}
				else
				{
					currentComponent = components.get(comp);
					currentComponentMap = currentComponent.returnLocalColorMap();
				}
				
				
			}
			
			else if(newGrid != null && comp != 0)
			{
				//System.out.println("Added component " + comp + " to [" + row + ", " + col + "]");
				
				currentGrid = newGrid;
				
				if(comp == 1)
				{

					//Store position of second component for iterating spacing
					row3 = row;
					col3 = col;
				}
				
				row += currentComponentMap.length + spacing;
				comp++;
				
				
				
				if(comp == components.size())
				{
					//System.out.println("All components added.");
					lastPlaced = new Point(row2, col2);
					return newGrid;
				}
				else
				{
					currentComponent = components.get(comp);
					currentComponentMap = currentComponent.returnLocalColorMap();
				}
			}
			
			else if(newGrid == null && comp == 0)
			{
				//Exhaustive search starting at random point
				//Try cols, then rows
				if(rowsTried < maxRow)
				{
					//System.out.println("Try next col");
					row = (row + 1) % maxRow;
					rowsTried++;
				}
				else
				{
					//System.out.println("Try next row");
					row = (row + 1) % maxRow;
					rowsTried = 0;
					
					col = (col + 1) % maxCol;
					colsTried++;
					
					if(colsTried > maxCol)
					{
						//System.out.println("All possible spots failed.");
						return null;
					}
					
				}
			}
			else if (newGrid == null && comp == 1)
			{
				if(row < rows - currentComponentMap.length)
				{
					//System.out.println("Try next col");
					//Try next col
					row++;
					spacing++;
				}
				else
				{
					//System.out.println("Adding second component failed. Replace first component.");
					//Couldn't place second component. Look at next placement for first component.
					currentGrid = grid;
					currentComponentMap = components.get(0).returnLocalColorMap();
					comp = 0;
					row = row2;
					col = col2;
					forceFail = true;
				}
			}
			else if (newGrid == null && comp > 1)
			{
				//Couldn't place nth component. Spacing wrong for second component, perhaps.
				
				//Reset to state after placing first component
				
				//System.out.println("Adding component " + comp + " failed. Replace second component.");
				currentGrid = firstCompGrid;
				comp = 1;
				
				currentComponent = components.get(1);
				currentComponentMap = currentComponent.returnLocalColorMap();
				
				//Try placing the second component down one row
				row3++;
				row = row3;				
				spacing++;
			}
			else
			{
				return null;
			}
			
		}
		
		
		return null;
	}
	
	/**
	 *  Tries to add a composite puzzle to the grid.
	 *  It picks a random cell in the first row, and tries to add the
	 *  first component. If that succeeds, it tries to add each successive
	 *  component down that column.
	 *  Else, it tries adding the first component exhaustively.
	 * @param grid A color map.
	 * @param p A composite puzzle.
	 * @return The grid containing this puzzle if possible. Null if not.
	 */
	public Color[][] diagonalDownRightRandomSequencePlacement(Color[][] grid, CompositePuzzle p)
	{
		//System.out.println("Diagonal down-right sequence placement.");
		ArrayList<PuzzleComponent> components = p.getComponents();
		

		int maxRow = rows - p.getWidthSpaced();
		int maxCol = cols - p.getHeightSpaced();
		
		//Current row/col we are placing a component in
		int row = r.nextInt(rows);
		int col = r.nextInt(cols);
		
		//Choose initial point with best free space
		Point pp = freespace(grid, new Point(row, col));
		row = pp.x;
		col = pp.y;
		
		
		int row2 = 0;
		int col2 = 0;
		
		int row3 = 0;
		int col3 = 0;
		
		//Current component we are placing
		int comp = 0;
		
		//How many columns we have tried when placing the first component
		int rowsTried = 0;
		int colsTried = 0;
		
		//Even spacing between letters
		int spacing = 1;
		
		//Has the puzzle been placed yet?
		boolean placed = false;
		boolean forceFail = false;
		
		PuzzleComponent currentComponent = components.get(comp);
		Color[][] currentComponentMap = currentComponent.returnLocalColorMap();
		
		Color[][] currentGrid = grid;
		Color[][] newGrid = grid;
		
		//Grid containing the placed first component
		Color[][] firstCompGrid = grid;
		
		Point pt = new Point(col, row);
		
		while(!placed)
		{
			pt = new Point(col,row); //Point to try placing the current component
			
			if(!forceFail)
				newGrid = Helper.superimpose(currentGrid, currentComponentMap, pt);
			else
			{
				newGrid = null;
				forceFail = false;
			}
				
			
			if(newGrid != null && comp == 0)
			{
				//Added first component successfully
				//System.out.println("Added first component to [" + row + ", " + col + "]");
				
				currentGrid = newGrid;
				
				//Store this so we can iterate on spacing if necessary.
				firstCompGrid = newGrid;
				
				//Store position of first component for possible iteration.
				row2 = row;
				col2 = col;
				
				spacing = 1;
				
				//Look at next row
				row += currentComponentMap.length + spacing;
				col += currentComponentMap[0].length + spacing;
				comp++;
				
				
				
				
				//Added all components, success
				if(comp == components.size())
				{
					//System.out.println("All components added.");
					lastPlaced = new Point(row2, col2);
					return newGrid;
				}
				else
				{
					currentComponent = components.get(comp);
					currentComponentMap = currentComponent.returnLocalColorMap();
				}
				
				
			}
			
			else if(newGrid != null && comp != 0)
			{
				//System.out.println("Added component " + comp + " to [" + row + ", " + col + "]");
				
				currentGrid = newGrid;
				
				if(comp == 1)
				{

					//Store position of second component for iterating spacing
					row3 = row;
					col3 = col;
				}
				
				row += currentComponentMap.length + spacing;
				col += currentComponentMap[0].length + spacing;
				comp++;
				
				
				
				if(comp == components.size())
				{
					//System.out.println("All components added.");
					lastPlaced = new Point(row2, col2);
					return newGrid;
				}
				else
				{
					currentComponent = components.get(comp);
					currentComponentMap = currentComponent.returnLocalColorMap();
				}
			}
			
			else if(newGrid == null && comp == 0)
			{
				//Exhaustive search starting at random point
				//Try cols, then rows
				if(rowsTried < maxRow)
				{
					//System.out.println("Try next col");
					row = (row + 1) % maxRow;
					rowsTried++;
				}
				else
				{
					//System.out.println("Try next row");
					row = (row + 1) % maxRow;
					rowsTried = 0;
					
					col = (col + 1) % maxCol;
					colsTried++;
					
					if(colsTried > maxCol)
					{
						//System.out.println("All possible spots failed.");
						return null;
					}
					
				}
			}
			else if (newGrid == null && comp == 1)
			{
				if(row < rows - currentComponentMap[0].length && col < cols - currentComponentMap.length)
				{
					//System.out.println("Try [" + row + ", " + col + "]");
					//Try next col
					row++;
					col++;
					spacing++;
				}
				else
				{
					//System.out.println("Adding second component failed. Replace first component.");
					//Couldn't place second component. Look at next placement for first component.
					currentGrid = grid;
					currentComponentMap = components.get(0).returnLocalColorMap();
					comp = 0;
					row = row2;
					col = col2;
					forceFail = true;
				}
			}
			else if (newGrid == null && comp > 1)
			{
				//Couldn't place nth component. Spacing wrong for second component, perhaps.
				
				//Reset to state after placing first component
				
				//System.out.println("Adding component " + comp + " failed. Replace second component.");
				currentGrid = firstCompGrid;
				comp = 1;
				
				currentComponent = components.get(1);
				currentComponentMap = currentComponent.returnLocalColorMap();
				
				//Try placing the second component to the right one column
				row3++;
				col3++;
				row = row3;
				col = col3;
				spacing++;
			}
			else
			{
				return null;
			}
			
		}
		
		
		return null;
	}
	
	/**
	 *  Tries to add a composite puzzle to the grid.
	 *  It picks a random cell in the first row, and tries to add the
	 *  first component. If that succeeds, it tries to add each successive
	 *  component down that column.
	 *  Else, it tries adding the first component exhaustively.
	 * @param grid A color map.
	 * @param p A composite puzzle.
	 * @return The grid containing this puzzle if possible. Null if not.
	 */
	public Color[][] horizontalSequencePlacement(Color[][] grid, Puzzle p)
	{
		//System.out.println("Horizontal sequence placement.");
		ArrayList<PuzzleComponent> components = p.getComponents();
		
		//Current row/col we are placing a component in
		int row = r.nextInt(rows);
		int col = 0;
		
		//Current component we are placing
		int comp = 0;
		
		//How many columns we have tried when placing the first component
		int rowsTried = 0;
		
		//Has the puzzle been placed yet?
		boolean placed = false;
		
		PuzzleComponent currentComponent = components.get(comp);
		Color[][] currentComponentMap = currentComponent.returnLocalColorMap();
		
		Color[][] currentGrid = grid;
		Color[][] newGrid = grid;
		
		Point pt = new Point(col, row);
		
		while(!placed)
		{
			pt = new Point(col,row);
			newGrid = Helper.superimpose(currentGrid, currentComponentMap, pt);
			
			if(newGrid != null)
			{
				//Added component successfully.
				//System.out.println("Added component " + comp + " to [" + row + ", " + col + "]");
				
				//Keep the new grid.
				currentGrid = newGrid;
				
				//Look at the row beneath the added com
				col += currentComponentMap[0].length + 1;
				comp += 1;
				
				//Added all components - return success
				if(comp == components.size())
				{
					//System.out.println("All components successfully added.");
					return newGrid;
				}
					
				
				//else, prepare to add next component
				currentComponent = components.get(comp);
				currentComponentMap = currentComponent.returnLocalColorMap();
			}
			else if(newGrid == null && comp == 0 && rowsTried < rows)
			{
				//Failed to add first component
				//Check next column, wrapping if necessary.
				////System.out.println("Failed to add first component to [" + row + ", " + col + "]");
				////System.out.println("Looking at next column");
				row = (row + 1) % rows;
				rowsTried++;
			}
			else if(newGrid == null && comp == 0 && col < cols)
			{
				//Failed to add first component to each column in a row
				////System.out.println("Failed to add first component to row " + row);
				////System.out.println("Checking next row");
				//Check next row
				row = (row + 1) % rows;
				rowsTried = 0;
				col++;
			}
			else if(newGrid == null && comp == 0 && col == cols)
			{
				//Cannot add first component, return null.
				//System.out.println("Cannot add first component anywhere");
				return null;
			}
			else if(newGrid == null && col < cols)
			{
				////System.out.println("Cannot add component " + comp + " to row " + row);
				//Cannot add nth component.
				//Check next row.
				//Might want code to ensure equal spacing?
				col++;
			}
			else
			{
				//Cannot place all components.
				return null;
			}
		}
		
		
		return null;
	}
	
	public Color[][] generateInitialColorMap(Grid grid)
	{
		int rows = grid.rows;
		int cols = grid.cols;
		
		Color[][] map = new Color[rows][cols];
		
		for(int i = 0; i < rows; i++)
			for(int j = 0; j < cols; j++)
			{
				if(grid.datagrid[i][j])
					map[i][j] = Constants.COLOR_OBSTACLE;
				else
					map[i][j] = Constants.COLOR_CLEAR;
			}
		
		return map;
	}
	
}
